package leetcode.editor.cn;

/*
    @author:yangwk
    @date:2023/3/21
    @description:
        */

public class P105ConstructBinaryTreeFromPreorderandInorderTraversal {
    int index = 0;

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7}, inorder = {9, 3, 15, 20, 7};
        P105ConstructBinaryTreeFromPreorderandInorderTraversal solution
                = new P105ConstructBinaryTreeFromPreorderandInorderTraversal();
        TreeNode root = solution.buildTree(preorder, inorder);
        System.out.println(root);

    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, inorder.length - 1);
    }

    // Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    // Output: [3,9,20,null,null,15,7]
    public TreeNode buildTree(int[] preorder, int[] inorder, int start, int end) {
        if (end < 0 || start > preorder.length - 1 || start > end) {
            return null;
        }
        int value = preorder[index++];
        TreeNode root = new TreeNode(value);
        Integer integer = find(inorder, value, start, end);
        if (integer == -1) {
            return root;
        }
        root.left = buildTree(preorder, inorder, start, integer - 1);
        root.right = buildTree(preorder, inorder, integer + 1, end);
        return root;
    }

    public Integer find(int[] arr, int value, int start, int end) {
        for (int i = start; i <= end; i++) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }

    //      Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
